#include <stdio.h>
#include <stdlib.h>

// 二叉树节点结构
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
};

// 路径数组结构
struct PathArray {
    int *path;
    int size;
};

// 创建新节点
struct TreeNode* createNode(int val) {
    struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    node->val = val;
    node->left = NULL;
    node->right = NULL;
    return node;
}

// 打印路径
void printPath(int path[], int pathSize) {
    printf("路径: ");
    for (int i = 0; i < pathSize; i++) {
        printf("%d", path[i]);
        if (i < pathSize - 1) {
            printf(" -> ");
        }
    }
    printf("\n");
}

// 递归查找路径
void findPathRecursive(struct TreeNode* root, int targetSum, 
                      int path[], int pathSize, int currentSum) {
    if (root == NULL) return;
    
    // 添加当前节点到路径
    path[pathSize] = root->val;
    pathSize++;
    currentSum += root->val;
    
    // 如果是叶子节点且路径和等于目标值，打印路径
    if (root->left == NULL && root->right == NULL && currentSum == targetSum) {
        printPath(path, pathSize);
    }
    
    // 递归遍历左右子树
    findPathRecursive(root->left, targetSum, path, pathSize, currentSum);
    findPathRecursive(root->right, targetSum, path, pathSize, currentSum);
}

// 主函数：查找和为指定值的所有路径
void findPaths(struct TreeNode* root, int targetSum) {
    if (root == NULL) {
        printf("树为空！\n");
        return;
    }
    
    int path[1000]; // 假设路径长度不超过1000
    printf("查找和为 %d 的所有路径：\n", targetSum);
    findPathRecursive(root, targetSum, path, 0, 0);
}

// 测试函数
void testBinaryTreePaths() {
    printf("=== C语言测试 ===\n");
    
    // 构建测试树1
    //       5
    //      / \
    //     4   8
    //    /   / \
    //   11  13  4
    //  /  \      \
    // 7    2      1
    struct TreeNode* root1 = createNode(5);
    root1->left = createNode(4);
    root1->right = createNode(8);
    root1->left->left = createNode(11);
    root1->right->left = createNode(13);
    root1->right->right = createNode(4);
    root1->left->left->left = createNode(7);
    root1->left->left->right = createNode(2);
    root1->right->right->right = createNode(1);
    
    // 测试1：查找和为22的路径
    printf("\n测试1：\n");
    findPaths(root1, 22);
    
    // 测试2：查找和为18的路径
    printf("\n测试2：\n");
    findPaths(root1, 18);
    
    // 构建测试树2
    //   1
    //  / \
    // 2   3
    struct TreeNode* root2 = createNode(1);
    root2->left = createNode(2);
    root2->right = createNode(3);
    
    // 测试3：查找和为5的路径
    printf("\n测试3：\n");
    findPaths(root2, 5);
    
    // 测试4：查找和为4的路径
    printf("\n测试4：\n");
    findPaths(root2, 4);
    
    // 释放内存（简单起见，这里不详细释放）
}

int main() {
    testBinaryTreePaths();
    return 0;
}
